//分割等和子集
class Solution {
public:
    bool canPartition(vector<int>& nums) 
    {
        int sum=0;
        for(auto e:nums) sum+=e;
        if(sum%2==1) return false;
        int target=sum/2;
        //背包大小为target 能否被装满
        vector<int>dp(target+1,0);
        for(int i=0;i<nums.size();i++)
        {
            for(int j=target;j>=nums[i];j--)
            {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target]==target;
    }
};
//最后一块石头的重量II
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        //分成两个背包 价值和重量是1:1的
        //计算总和 求 dp[sum/2] 再拿 abs( (sum-dp[sum/2])-dp[sum/2] )
        int sum=0;
        for(auto e:stones) sum+=e;
        int target=sum/2;
        vector<int>dp(target+1,0);
        for(int i=0;i<stones.size();i++)
        {
            for(int j=target;j>=stones[i];j--)
            {
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return abs(sum-2*dp[sum/2]);
    }
};
//目标和
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        //一堆正数 一堆负数 正数和+负数和=target
        //计算有有几种方法即可
        //所有数的和为sum 设正数部分的和为a 则负数部分的和为sum-a
        //a-(sum-a)=target a=(target+sum)/2
        int sum=0;
        for(auto e:nums) sum+=e;
        if(abs(target)> sum) return 0;
        if((target+sum)%2==1) return 0;
        int require=(target+sum)/2;
        //求把背包装满有几种方法 而不是求背包能装的最大价值
        vector<int>dp(require+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++)
        {
            for(int j=require;j>=nums[i];j--)
            {
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[require];
    }
};
//一和零
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        //1个背包 同时要装0和1 0和1对应的容量分别是m和n 
        //物品是 strs[]
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        //求背包的最大容量
        for(auto str:strs)
        {
            //物品的数量就在str里面
            int s0=0,s1=0;
            for(auto ch:str)
            {
                if(ch=='0') s0++;
                else s1++;
            }
            //物品有了
            for(int i=m;i>=s0;i--)
            {
                for(int j=n;j>=s1;j--)
                {
                    dp[i][j]=max(dp[i][j],dp[i-s0][j-s1]+1);
                }
            }
        }
        return dp[m][n];
    }
};